﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.StringCode
{
    class ReplaceString
    {
        //======================================== 剑指offer 05 替换空格
        //请实现一个函数，把字符串s中的每个空格替换成"%20"
        public string ReplaceSpace(string s)
        {   //扩充数组到每隔空格替换成"%20"之后的大小
            //然后从后向前替换空格，也就是双指针法
            //从前向后填充就是O(n^2)的算法，因为每次添加元素都要将添加元素之后的所有元素向后移动
            //很多数组填充类问题，都可以预先给数组扩容，然后从后向前操作
            //这样不用申请新数组，同时也避免了每次添加元素都要移动所有的元素
            //时间复杂度：O(n)
            //空间复杂度：O(1)

            int count = 0;//计算空格个数
            int len = s.Length;
            foreach(char i in s)
            {
                if (i == ' ')
                    count++;
            }

            char[] arr = new char[len + count * 2];//扩充字符串大小
            s.ToArray().CopyTo(arr, 0);
            //从后向前替换
            int left = len - 1;
            int right = arr.Length - 1;
            while(left < right && left >= 0)
            {
                if(arr[left] == ' ')
                {
                    arr[right--] = '0';
                    arr[right--] = '2';
                    arr[right--] = '%';
                }
                else
                {
                    arr[right--] = arr[left];
                }
                left--;

            }

            return new string(arr);
        }
    }
}
